#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    Node *next;
}Node;

void headInsert(Node **head, int data);//头部插入
void tailInsert(Node *head, int data);//尾部插入
void Insert(Node **head, int data, int pos);//指定位置插入
void Remove(Node **head, int pos);//指定位置删除
void Print(Node *node);//遍历打印
void Reverse(Node **head);//翻转

void headInsert(Node **head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void tailInsert(Node *head, int data) {
    Node *current = head;
    while(current->next != NULL) {
        current = current->next;
    }
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    current->next = newNode;
}

void Insert(Node **head, int data, int pos) {
    Node *current = *head;
    Node *previous = NULL;
    Node *next = NULL;
    if(pos < 1) {
        printf("ERROR: Invalid position.\n");
        return;
    }
    if(pos == 1) {
        headInsert(head, data);
        return;
    }
    for(int i = 0; i < pos - 1; i++) {
        if(current == NULL) {
            printf("ERROR:Out of index.\n");
            return;
        } else {
            previous = current;
            current = current->next;
        } 
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = current;
    previous->next = newNode;
}

void Remove(Node **head, int pos) {
    if(*head == NULL) {
        printf("ERROR:empty link list.\n");
        return;
    }
    Node *current = *head;
    Node *previous = NULL;
    Node *next = NULL;
    //Remove tail
    if(pos == -1) {
        while(current->next != NULL) {
            previous = current;
            current = current->next;
        }
        previous->next = NULL;
        free(current);
    }
    else if(pos == 1) {
        *head = current->next;
        free(current);
    }
    else if(pos > 0) {
        for(int i = 0; i < pos - 1; i++) {
            previous = current;
            current = current->next;
            next = current->next;
        }
        previous->next = next;
        free(current);
    }
    else {
        printf("ERROR:invalid index.\n");
    }
    return;
}

void Print(Node *node) {
    if(node == NULL) {
        printf("NULL\n");
        return;
    }
    Node *current = node;
    while(current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void Reverse(Node **head) {
    if(*head == NULL) return;
    Node *current = *head;
    Node *previous = NULL;
    Node *next = (*head)->next;
    while(current != NULL) {
        current->next = previous;
        previous = current;
        current = next;
        if(next == NULL) break;
        next = next->next;
    }
    *head = previous;
}

int main(void) {
    Node *head = NULL;
    headInsert(&head, 2);//2
    headInsert(&head, 8);//8 2
    headInsert(&head, 4);//4 8 2
    tailInsert(head, 6);//4 8 2 6
    Insert(&head, 5, 2);//4 5 8 2 6
    Remove(&head, -1);//4 5 8 2
    Remove(&head, 1);//5 8 2
    Reverse(&head);//2 8
    Print(head);
    return 0;
}